home *** CD-ROM | disk | FTP | other *** search
/ Almathera Ten Pack 2: CDPD 1 / Almathera Ten on Ten - Disc 2: CDPD 1.iso / pd / 201-225 / 223 / iff2sun / convert.c next >
C/C++ Source or Header  |  1995-03-13  |  21KB  |  852 lines
  1.  
  2. /*
  3.  * Apply median cut on an image.
  4.  *
  5.  * median [-c n] [-f] input output
  6.  *     -c n        - set colortable size.  Default is 256.
  7.  *     -f        - use Floyd-Steinberg dithering.
  8.  *     -lzw        - compress output with LZW
  9.  *     -none        - use no compression on output
  10.  *     -picio        - use picio compression on output
  11.  *     -packbits    - use packbits compression on output
  12.  *     -rowsperstrip n    - create output with n rows/strip of data
  13.  * (by default the compression scheme and rows/strip are taken
  14.  *  from the input file)
  15.  *
  16.  * Notes:
  17.  *
  18.  * [1] Floyd-Steinberg dither:
  19.  *  I should point out that the actual fractions we used were, assuming
  20.  *  you are at X, moving left to right:
  21.  *
  22.  *            X     7/16
  23.  *         3/16   5/16  1/16    
  24.  *
  25.  *  Note that the error goes to four neighbors, not three.  I think this
  26.  *  will probably do better (at least for black and white) than the
  27.  *  3/8-3/8-1/4 distribution, at the cost of greater processing.  I have
  28.  *  seen the 3/8-3/8-1/4 distribution described as "our" algorithm before,
  29.  *  but I have no idea who the credit really belongs to.
  30.  
  31.  *  Also, I should add that if you do zig-zag scanning (see my immediately
  32.  *  previous message), it is sufficient (but not quite as good) to send
  33.  *  half the error one pixel ahead (e.g. to the right on lines you scan
  34.  *  left to right), and half one pixel straight down.  Again, this is for
  35.  *  black and white;  I've not tried it with color.
  36.  *  -- 
  37.  *                        Lou Steinberg
  38.  *
  39.  * [2] Color Image Quantization for Frame Buffer Display, Paul Heckbert,
  40.  *    Siggraph '82 proceedings, pp. 297-307
  41.  */
  42. #include <stdio.h>
  43. #include <sys/types.h>
  44. #include <rasterfile.h>
  45.  
  46. #define    MAX_CMAP_SIZE    256
  47. #define    howmany(x, y)    (((x)+((y)-1))/(y))
  48. #define    streq(a,b)    (strcmp(a,b) == 0)
  49.  
  50. #define    COLOR_DEPTH    8
  51. #define    MAX_COLOR    256
  52.  
  53. #define    B_DEPTH        4        /* # bits/pixel to use */
  54. #define    B_LEN        (1<<B_DEPTH)
  55.  
  56. #define    C_DEPTH        2
  57. #define    C_LEN        (1<<C_DEPTH)    /* # cells/color to use */
  58.  
  59. #define    COLOR_SHIFT    (COLOR_DEPTH-B_DEPTH)
  60. #define COMPRESSION_NONE 0
  61. #define COMPRESSION_PACKBITS 1
  62. #define COMPRESSION_LZW 2
  63. #define COMPRESSION_PICIO 3
  64.  
  65.  
  66. typedef    struct colorbox {
  67.     struct    colorbox *next, *prev;
  68.     int    rmin, rmax;
  69.     int    gmin, gmax;
  70.     int    bmin, bmax;
  71.     int    total;
  72. } Colorbox;
  73.  
  74. typedef struct {
  75.     int    num_ents;
  76.     int    entries[MAX_CMAP_SIZE][2];
  77. } C_cell;
  78.  
  79. u_short    rm[MAX_CMAP_SIZE], gm[MAX_CMAP_SIZE], bm[MAX_CMAP_SIZE];
  80. int    bytes_per_pixel;
  81. long    num_colors, width, hieght, length;
  82. int    histogram[B_LEN][B_LEN][B_LEN];
  83. Colorbox *freeboxes;
  84. Colorbox *usedboxes;
  85. Colorbox *largest_box();
  86. C_cell    **ColorCells;
  87. FILE    *in, *out;
  88.  
  89. char    *usage = "usage: median [-c n] [-f] [-none] [-lzw] [-picio] [-packbits] [-rowsperstrip r] input output\n";
  90.  
  91. main(argc, argv)
  92.     int argc;
  93.     char **argv;
  94. {
  95.     struct rasterfile header;
  96.     int i, j, dither = 0;
  97.     long chunk;
  98.     char *ifile_name = NULL, *ofile_name = NULL, color;
  99.     Colorbox *box_list, *ptr;
  100.     u_short rowsperstrip = 128, compression = -1, shortv;
  101.     u_short bitspersample, samplesperpixel, photometric;
  102.     float floatv;
  103.  
  104.     num_colors = MAX_CMAP_SIZE;
  105.     for (argc--, argv++; argc > 0 && argv[0][0] == '-'; argc--, argv++) {
  106.         if (streq(argv[0], "-f")) {
  107.             dither = 1;
  108.             continue;
  109.         }
  110.         if (streq(argv[0], "-c")) {
  111.             argc--, argv++;
  112.             if (argc < 1) {
  113.                 fprintf(stderr, "-c: missing colormap size\n%s",
  114.                     usage);
  115.                 exit(1);
  116.             }
  117.             num_colors = atoi(argv[0]);
  118.             if (num_colors > MAX_CMAP_SIZE) {
  119.                 fprintf(stderr,
  120.                    "-c: colormap too big, max %d\n%s",
  121.                    MAX_CMAP_SIZE, usage);
  122.                 exit(1);
  123.             }
  124.             continue;
  125.         }
  126.         if (streq(argv[0], "-none")) {
  127.             compression = COMPRESSION_NONE;
  128.             continue;
  129.         }
  130.         if (streq(argv[0], "-packbits")) {
  131.             compression = COMPRESSION_PACKBITS;
  132.             continue;
  133.         }
  134.         if (streq(argv[0], "-lzw")) {
  135.             compression = COMPRESSION_LZW;
  136.             continue;
  137.         }
  138.         if (streq(argv[0], "-picio")) {
  139.             compression = COMPRESSION_PICIO;
  140.             continue;
  141.         }
  142.         if (streq(argv[0], "-rowsperstrip")) {
  143.             argc--, argv++;
  144.             rowsperstrip = atoi(argv[0]);
  145.             continue;
  146.         }
  147.         fprintf(stderr, "%s: unknown option\n%s", argv[0], usage);
  148.         exit(1);
  149.     }
  150.     if (argc < 2) {
  151.         fprintf(stderr, "%s", usage);
  152.         exit(-1);
  153.     }
  154.     in = fopen(argv[0], "r");
  155.     if (in == NULL)
  156.         exit(-1);
  157.  
  158.     fread(&width, 4, 1, in); /* Get size of picture */
  159.     fread(&hieght, 4, 1, in);
  160.     length = hieght;
  161.  
  162.     /*
  163.      * STEP 1:  create empty boxes
  164.      */
  165.     usedboxes = NULL;
  166.     box_list = freeboxes = (Colorbox *)malloc(num_colors*sizeof (Colorbox));
  167.     freeboxes[0].next = &freeboxes[1];
  168.     freeboxes[0].prev = NULL;
  169.     for (i = 1; i < num_colors-1; ++i) {
  170.         freeboxes[i].next = &freeboxes[i+1];
  171.         freeboxes[i].prev = &freeboxes[i-1];
  172.     }
  173.     freeboxes[num_colors-1].next = NULL;
  174.     freeboxes[num_colors-1].prev = &freeboxes[num_colors-2];
  175.  
  176.     /*
  177.      * STEP 2: get histogram, initialize first box
  178.      */
  179.     ptr = freeboxes;
  180.     freeboxes = ptr->next;
  181.     if (freeboxes)
  182.         freeboxes->prev = NULL;
  183.     ptr->next = usedboxes;
  184.     usedboxes = ptr;
  185.     if (ptr->next)
  186.         ptr->next->prev = ptr;
  187.     get_histogram(in, ptr);
  188.  
  189.     /*
  190.      * STEP 3: continually subdivide boxes until no more free
  191.      * boxes remain or until all colors assigned.
  192.      */
  193.     while (freeboxes != NULL) {
  194.         ptr = largest_box();
  195.         if (ptr != NULL)
  196.             splitbox(ptr);
  197.         else
  198.             freeboxes = NULL;
  199.     }
  200.  
  201.     /*
  202.      * STEP 4: assign colors to all boxes
  203.      */
  204.     for (i = 0, ptr = usedboxes; ptr != NULL; ++i, ptr = ptr->next) {
  205.         rm[i] = ((ptr->rmin + ptr->rmax) << COLOR_SHIFT) / 2;
  206.         gm[i] = ((ptr->gmin + ptr->gmax) << COLOR_SHIFT) / 2;
  207.         bm[i] = ((ptr->bmin + ptr->bmax) << COLOR_SHIFT) / 2;
  208.     }
  209.  
  210.     fprintf(stderr,"Number of colors used %d\n", i);
  211.  
  212.     /* We're done with the boxes now */
  213.     free(box_list);
  214.     box_list = freeboxes = usedboxes = NULL;
  215.  
  216.     /*
  217.      * STEP 5: scan histogram and map all values to closest color
  218.      */
  219.     /* 5a: create cell list as described in Heckbert[2] */
  220.     ColorCells = (C_cell **)calloc(C_LEN*C_LEN*C_LEN, sizeof (C_cell *));
  221.     /* 5b: create mapping from truncated pixel space to color
  222.        table entries */
  223.     map_colortable();
  224.  
  225.     /*
  226.      * STEP 6: scan image, match input values to table entries
  227.      */
  228.     out = fopen(argv[1], "w");
  229.     if (out == NULL)
  230.         exit(-2);
  231.  
  232.     header.ras_magic= 0x59a66a95;
  233.     header.ras_width= width;
  234.       header.ras_height= hieght;
  235.       header.ras_depth= 8;
  236.     header.ras_length= width * hieght;
  237.       header.ras_type= RT_STANDARD;
  238.       header.ras_maptype= RMT_EQUAL_RGB;
  239.       header.ras_maplength= 3*256;
  240.  
  241. /* Write out the rasterfile header to the ouput */
  242.  
  243.     fwrite(&header, sizeof(header), 1, out);
  244.  
  245. /* Write the colormap to the ouput */
  246.  
  247.     for(i=0;i<256;i++) {
  248.       color = (char)rm[i];
  249.       fwrite(&color, 1, 1, out);
  250.     }
  251.  
  252.     for(i=0;i<256;i++) {
  253.       color = (char)gm[i];
  254.       fwrite(&color, 1, 1, out);
  255.     }
  256.  
  257.     for(i=0;i<256;i++) {
  258.       color = (char)bm[i];
  259.       fwrite(&color, 1, 1, out);
  260.     }
  261.  
  262.     rewind(in);        /* rewind input file XXX */
  263.  
  264.     fread(&chunk, 4, 1, in);
  265.     fread(&chunk, 4, 1, in);
  266.     if (dither)
  267.         quant_fsdither(in, out);
  268.     else
  269.         quant(in, out);
  270.     (void) fclose(out);
  271.  
  272. }
  273.  
  274. static
  275. get_histogram(in, box)
  276.     FILE *in;
  277.     register Colorbox *box;
  278. {
  279.     register u_char *inptr;
  280.     register int red, green, blue, j, i;
  281.     u_char *inline;
  282.  
  283.     i = 24 * width;
  284.     inline = (u_char *)malloc(howmany(i, 8));
  285.     if (inline == NULL) {
  286.         fprintf(stderr, "No space for scanline buffer\n");
  287.         exit(-1);
  288.     }
  289.     box->rmin = box->gmin = box->bmin = 999;
  290.     box->rmax = box->gmax = box->bmax = -1;
  291.     box->total = width * length;
  292.  
  293.     { register int *ptr = &histogram[0][0][0];
  294.       for (i = B_LEN*B_LEN*B_LEN; --i >= 0;)
  295.         *ptr++ = 0;
  296.     }
  297.     for (i = length; i-- > 0;) {
  298.         if (fread(inline, width*3, 1, in) <= 0)
  299.             break;
  300.         inptr = inline;
  301.         for (j = width; j-- > 0;) {
  302.             red = *inptr++ >> COLOR_SHIFT;
  303.             green = *inptr++ >> COLOR_SHIFT;
  304.             blue = *inptr++ >> COLOR_SHIFT; 
  305.             if (red < box->rmin)
  306.                 box->rmin = red;
  307.                 if (red > box->rmax)
  308.                 box->rmax = red;
  309.                 if (green < box->gmin)
  310.                 box->gmin = green;
  311.                 if (green > box->gmax)
  312.                 box->gmax = green;
  313.                 if (blue < box->bmin)
  314.                 box->bmin = blue;
  315.                 if (blue > box->bmax)
  316.                 box->bmax = blue;
  317.                 histogram[red][green][blue]++;
  318.         }
  319.     }
  320.     free(inline);
  321. }
  322.  
  323. static Colorbox *
  324. largest_box()
  325. {
  326.     register Colorbox *p, *b;
  327.     register int size;
  328.  
  329.     b = NULL;
  330.     size = -1;
  331.     for (p = usedboxes; p != NULL; p = p->next)
  332.         if ((p->rmax > p->rmin || p->gmax > p->gmin ||
  333.             p->bmax > p->bmin) &&  p->total > size)
  334.                 size = (b = p)->total;
  335.     return (b);
  336. }
  337.  
  338. static
  339. splitbox(ptr)
  340.     register Colorbox *ptr;
  341. {
  342.     int        hist2[B_LEN];
  343.     int        first, last;
  344.     register Colorbox    *new;
  345.     register int    *iptr, *histp;
  346.     register int    i, j;
  347.     register int    ir,ig,ib;
  348.     register int sum, sum1, sum2;
  349.     int        total;
  350.     enum { RED, GREEN, BLUE } axis;
  351.  
  352.     /*
  353.      * See which axis is the largest, do a histogram along that
  354.      * axis.  Split at median point.  Contract both new boxes to
  355.      * fit points and return
  356.      */
  357.     i = ptr->rmax - ptr->rmin;
  358.     if (i >= ptr->gmax - ptr->gmin  && i >= ptr->bmax - ptr->bmin)
  359.         axis = RED;
  360.     else if (ptr->gmax - ptr->gmin >= ptr->bmax - ptr->bmin)
  361.         axis = GREEN;
  362.     else
  363.         axis = BLUE;
  364.     /* get histogram along longest axis */
  365.     switch (axis) {
  366.     case RED:
  367.         histp = &hist2[ptr->rmin];
  368.             for (ir = ptr->rmin; ir <= ptr->rmax; ++ir) {
  369.             *histp = 0;
  370.             for (ig = ptr->gmin; ig <= ptr->gmax; ++ig) {
  371.                 iptr = &histogram[ir][ig][ptr->bmin];
  372.                 for (ib = ptr->bmin; ib <= ptr->bmax; ++ib)
  373.                     *histp += *iptr++;
  374.             }
  375.             histp++;
  376.             }
  377.             first = ptr->rmin;
  378.         last = ptr->rmax;
  379.             break;
  380.     case GREEN:
  381.             histp = &hist2[ptr->gmin];
  382.             for (ig = ptr->gmin; ig <= ptr->gmax; ++ig) {
  383.             *histp = 0;
  384.             for (ir = ptr->rmin; ir <= ptr->rmax; ++ir) {
  385.                 iptr = &histogram[ir][ig][ptr->bmin];
  386.                 for (ib = ptr->bmin; ib <= ptr->bmax; ++ib)
  387.                     *histp += *iptr++;
  388.             }
  389.             histp++;
  390.             }
  391.             first = ptr->gmin;
  392.         last = ptr->gmax;
  393.             break;
  394.     case BLUE:
  395.             histp = &hist2[ptr->bmin];
  396.             for (ib = ptr->bmin; ib <= ptr->bmax; ++ib) {
  397.             *histp = 0;
  398.             for (ir = ptr->rmin; ir <= ptr->rmax; ++ir) {
  399.                 iptr = &histogram[ir][ptr->gmin][ib];
  400.                 for (ig = ptr->gmin; ig <= ptr->gmax; ++ig) {
  401.                     *histp += *iptr;
  402.                     iptr += B_LEN;
  403.                 }
  404.             }
  405.             histp++;
  406.             }
  407.             first = ptr->bmin;
  408.         last = ptr->bmax;
  409.             break;
  410.     }
  411.     /* find median point */
  412.     histp = &hist2[first];
  413.     sum2 = ptr->total / 2;
  414.     histp = &hist2[first];
  415.     sum = 0;
  416.     for (i = first; i <= last && (sum += *histp++) < sum2; ++i)
  417.         ;
  418.     if (i == first)
  419.         i++;
  420.  
  421.     /* Create new box, re-allocate points */
  422.     new = freeboxes;
  423.     freeboxes = new->next;
  424.     if (freeboxes)
  425.         freeboxes->prev = NULL;
  426.     if (usedboxes)
  427.         usedboxes->prev = new;
  428.     new->next = usedboxes;
  429.     usedboxes = new;
  430.  
  431.     total = ptr->total;
  432.     histp = &hist2[first];
  433.     for (sum1 = 0, j = first; j < i; j++)
  434.         sum1 += *histp++;
  435.     for (sum2 = 0, j = i; j <= last; j++)
  436.         sum2 += *histp++;
  437.     new->total = sum1;
  438.     ptr->total = sum2;
  439.  
  440.     new->rmin = ptr->rmin;
  441.     new->rmax = ptr->rmax;
  442.     new->gmin = ptr->gmin;
  443.     new->gmax = ptr->gmax;
  444.     new->bmin = ptr->bmin;
  445.     new->bmax = ptr->bmax;
  446.     switch (axis) {
  447.     case RED:
  448.         new->rmax = i-1;
  449.             ptr->rmin = i;
  450.             break;
  451.     case GREEN:
  452.             new->gmax = i-1;
  453.             ptr->gmin = i;
  454.             break;
  455.     case BLUE:
  456.             new->bmax = i-1;
  457.             ptr->bmin = i;
  458.             break;
  459.     }
  460.     shrinkbox(new);
  461.     shrinkbox(ptr);
  462. }
  463.  
  464. static
  465. shrinkbox(box)
  466.     register Colorbox *box;
  467. {
  468.     register int *histp, ir, ig, ib;
  469.  
  470.     if (box->rmax > box->rmin) {
  471.         for (ir = box->rmin; ir <= box->rmax; ++ir)
  472.             for (ig = box->gmin; ig <= box->gmax; ++ig) {
  473.                 histp = &histogram[ir][ig][box->bmin];
  474.                     for (ib = box->bmin; ib <= box->bmax; ++ib)
  475.                     if (*histp++ != 0) {
  476.                         box->rmin = ir;
  477.                         goto have_rmin;
  478.                     }
  479.             }
  480.     have_rmin:
  481.         if (box->rmax > box->rmin)
  482.             for (ir = box->rmax; ir >= box->rmin; --ir)
  483.                 for (ig = box->gmin; ig <= box->gmax; ++ig) {
  484.                     histp = &histogram[ir][ig][box->bmin];
  485.                     ib = box->bmin;
  486.                     for (; ib <= box->bmax; ++ib)
  487.                         if (*histp++ != 0) {
  488.                             box->rmax = ir;
  489.                             goto have_rmax;
  490.                         }
  491.                     }
  492.     }
  493. have_rmax:
  494.     if (box->gmax > box->gmin) {
  495.         for (ig = box->gmin; ig <= box->gmax; ++ig)
  496.             for (ir = box->rmin; ir <= box->rmax; ++ir) {
  497.                 histp = &histogram[ir][ig][box->bmin];
  498.                     for (ib = box->bmin; ib <= box->bmax; ++ib)
  499.                 if (*histp++ != 0) {
  500.                     box->gmin = ig;
  501.                     goto have_gmin;
  502.                 }
  503.             }
  504.     have_gmin:
  505.         if (box->gmax > box->gmin)
  506.             for (ig = box->gmax; ig >= box->gmin; --ig)
  507.                 for (ir = box->rmin; ir <= box->rmax; ++ir) {
  508.                     histp = &histogram[ir][ig][box->bmin];
  509.                     ib = box->bmin;
  510.                     for (; ib <= box->bmax; ++ib)
  511.                         if (*histp++ != 0) {
  512.                             box->gmax = ig;
  513.                             goto have_gmax;
  514.                         }
  515.                     }
  516.     }
  517. have_gmax:
  518.     if (box->bmax > box->bmin) {
  519.         for (ib = box->bmin; ib <= box->bmax; ++ib)
  520.             for (ir = box->rmin; ir <= box->rmax; ++ir) {
  521.                 histp = &histogram[ir][box->gmin][ib];
  522.                     for (ig = box->gmin; ig <= box->gmax; ++ig) {
  523.                     if (*histp != 0) {
  524.                         box->bmin = ib;
  525.                         goto have_bmin;
  526.                     }
  527.                     histp += B_LEN;
  528.                     }
  529.                 }
  530.     have_bmin:
  531.         if (box->bmax > box->bmin)
  532.             for (ib = box->bmax; ib >= box->bmin; --ib)
  533.                 for (ir = box->rmin; ir <= box->rmax; ++ir) {
  534.                     histp = &histogram[ir][box->gmin][ib];
  535.                     ig = box->gmin;
  536.                     for (; ig <= box->gmax; ++ig) {
  537.                         if (*histp != 0) {
  538.                             box->bmax = ib;
  539.                             goto have_bmax;
  540.                         }
  541.                         histp += B_LEN;
  542.                     }
  543.                     }
  544.     }
  545. have_bmax:
  546.     ;
  547. }
  548.  
  549. static C_cell *
  550. create_colorcell(red, green, blue)
  551.     int red, green, blue;
  552. {
  553.     register int ir, ig, ib, i;
  554.     register C_cell *ptr;
  555.     int mindist, next_n;
  556.     register int tmp, dist, n;
  557.  
  558.     ir = red >> (COLOR_DEPTH-C_DEPTH);
  559.     ig = green >> (COLOR_DEPTH-C_DEPTH);
  560.     ib = blue >> (COLOR_DEPTH-C_DEPTH);
  561.     ptr = (C_cell *)malloc(sizeof (C_cell));
  562.     *(ColorCells + ir*C_LEN*C_LEN + ig*C_LEN + ib) = ptr;
  563.     ptr->num_ents = 0;
  564.  
  565.     /*
  566.      * Step 1: find all colors inside this cell, while we're at
  567.      *       it, find distance of centermost point to furthest corner
  568.      */
  569.     mindist = 99999999;
  570.     for (i = 0; i < num_colors; ++i) {
  571.         if (rm[i]>>(COLOR_DEPTH-C_DEPTH) != ir  ||
  572.             gm[i]>>(COLOR_DEPTH-C_DEPTH) != ig  ||
  573.             bm[i]>>(COLOR_DEPTH-C_DEPTH) != ib)
  574.             continue;
  575.         ptr->entries[ptr->num_ents][0] = i;
  576.         ptr->entries[ptr->num_ents][1] = 0;
  577.         ++ptr->num_ents;
  578.             tmp = rm[i] - red;
  579.             if (tmp < (MAX_COLOR/C_LEN/2))
  580.             tmp = MAX_COLOR/C_LEN-1 - tmp;
  581.             dist = tmp*tmp;
  582.             tmp = gm[i] - green;
  583.             if (tmp < (MAX_COLOR/C_LEN/2))
  584.             tmp = MAX_COLOR/C_LEN-1 - tmp;
  585.             dist += tmp*tmp;
  586.             tmp = bm[i] - blue;
  587.             if (tmp < (MAX_COLOR/C_LEN/2))
  588.             tmp = MAX_COLOR/C_LEN-1 - tmp;
  589.             dist += tmp*tmp;
  590.             if (dist < mindist)
  591.             mindist = dist;
  592.     }
  593.  
  594.     /*
  595.      * Step 3: find all points within that distance to cell.
  596.      */
  597.     for (i = 0; i < num_colors; ++i) {
  598.         if (rm[i] >> (COLOR_DEPTH-C_DEPTH) == ir  &&
  599.             gm[i] >> (COLOR_DEPTH-C_DEPTH) == ig  &&
  600.             bm[i] >> (COLOR_DEPTH-C_DEPTH) == ib)
  601.             continue;
  602.         dist = 0;
  603.             if ((tmp = red - rm[i]) > 0 ||
  604.             (tmp = rm[i] - (red + MAX_COLOR/C_LEN-1)) > 0 )
  605.             dist += tmp*tmp;
  606.             if ((tmp = green - gm[i]) > 0 ||
  607.             (tmp = gm[i] - (green + MAX_COLOR/C_LEN-1)) > 0 )
  608.             dist += tmp*tmp;
  609.             if ((tmp = blue - bm[i]) > 0 ||
  610.             (tmp = bm[i] - (blue + MAX_COLOR/C_LEN-1)) > 0 )
  611.             dist += tmp*tmp;
  612.             if (dist < mindist) {
  613.             ptr->entries[ptr->num_ents][0] = i;
  614.             ptr->entries[ptr->num_ents][1] = dist;
  615.             ++ptr->num_ents;
  616.             }
  617.     }
  618.  
  619.     /*
  620.      * Sort color cells by distance, use cheap exchange sort
  621.      */
  622.     for (n = ptr->num_ents - 1; n > 0; n = next_n) {
  623.         next_n = 0;
  624.         for (i = 0; i < n; ++i)
  625.             if (ptr->entries[i][1] > ptr->entries[i+1][1]) {
  626.                 tmp = ptr->entries[i][0];
  627.                 ptr->entries[i][0] = ptr->entries[i+1][0];
  628.                 ptr->entries[i+1][0] = tmp;
  629.                 tmp = ptr->entries[i][1];
  630.                 ptr->entries[i][1] = ptr->entries[i+1][1];
  631.                 ptr->entries[i+1][1] = tmp;
  632.                 next_n = i;
  633.                 }
  634.     }
  635.     return (ptr);
  636. }
  637.  
  638. static
  639. map_colortable()
  640. {
  641.     register int *histp = &histogram[0][0][0];
  642.     register C_cell *cell;
  643.     register int j, tmp, d2, dist;
  644.     int ir, ig, ib, i;
  645.  
  646.     for (ir = 0; ir < B_LEN; ++ir)
  647.         for (ig = 0; ig < B_LEN; ++ig)
  648.             for (ib = 0; ib < B_LEN; ++ib, histp++) {
  649.                 if (*histp == 0) {
  650.                     *histp = -1;
  651.                     continue;
  652.                 }
  653.                 cell = *(ColorCells +
  654.                     (((ir>>(B_DEPTH-C_DEPTH)) << C_DEPTH*2) +
  655.                     ((ig>>(B_DEPTH-C_DEPTH)) << C_DEPTH) +
  656.                     (ib>>(B_DEPTH-C_DEPTH))));
  657.                 if (cell == NULL )
  658.                     cell = create_colorcell(
  659.                         ir << COLOR_SHIFT,
  660.                         ig << COLOR_SHIFT,
  661.                         ib << COLOR_SHIFT);
  662.                 dist = 9999999;
  663.                 for (i = 0; i < cell->num_ents &&
  664.                     dist > cell->entries[i][1]; ++i) {
  665.                     j = cell->entries[i][0];
  666.                     d2 = rm[j] - (ir << COLOR_SHIFT);
  667.                     d2 *= d2;
  668.                     tmp = gm[j] - (ig << COLOR_SHIFT);
  669.                     d2 += tmp*tmp;
  670.                     tmp = bm[j] - (ib << COLOR_SHIFT);
  671.                     d2 += tmp*tmp;
  672.                     if (d2 < dist) {
  673.                         dist = d2;
  674.                         *histp = j;
  675.                     }
  676.                 }
  677.             }
  678. }
  679.  
  680. /*
  681.  * straight quantization.  Each pixel is mapped to the colors
  682.  * closest to it.  Color values are rounded to the nearest color
  683.  * table entry.
  684.  */
  685. static
  686. quant(in, out)
  687.     FILE *in, *out;
  688. {
  689.     u_char    *outline, *inline;
  690.     register u_char    *outptr, *inptr;
  691.     register int i, j, red, green, blue;
  692.  
  693.     i = 24 * width;
  694.     inline = (u_char *)malloc(howmany(i, 8));
  695.     outline = (u_char *)malloc(width);
  696.     for (i = 0; i < length; i++) {
  697.         if (fread(inline, 3*width, 1, in) <= 0)
  698.             break;
  699.         inptr = inline;
  700.         outptr = outline;
  701.         for (j = 0; j < width; j++) {
  702.             red = *inptr++ >> COLOR_SHIFT;
  703.             green = *inptr++ >> COLOR_SHIFT;
  704.             blue = *inptr++ >> COLOR_SHIFT;
  705.             *outptr++ = histogram[red][green][blue];
  706.         }
  707.         if (fwrite(outline, width, 1, out) <= 0)
  708.             break;
  709.     }
  710.     free(inline);
  711.     free(outline);
  712. }
  713.  
  714. static
  715. quant_fsdither(in, out)
  716.     FILE *in, *out;
  717. {
  718.     u_char *outline, *inline, *inptr;
  719.     short *thisline, *nextline, *tmpptr;
  720.     register u_char    *outptr;
  721.     register short *thisptr, *nextptr;
  722.     register int i, j, tmp;
  723.     int imax, jmax, lastline, lastpixel;
  724.  
  725.     imax = length - 1;
  726.     jmax = width - 1;
  727.     i = 12 * width;
  728.     inline = (u_char *)malloc(howmany(i, 8));
  729.     thisline = (short *)malloc(width * 3 * sizeof (short));
  730.     nextline = (short *)malloc(width * 3 * sizeof (short));
  731.     outline = (unsigned char *) malloc(width);
  732.  
  733.     /*
  734.      * Get first line
  735.      */
  736.     if (fread(inline, 3*width, 1, in) <= 0)
  737.         return;
  738.     inptr = inline;
  739.     nextptr = nextline;
  740.     for (j = 0; j < width; ++j) {
  741.         *nextptr++ = *inptr++;
  742.         *nextptr++ = *inptr++;
  743.         *nextptr++ = *inptr++;
  744.     }
  745.     for (i = 0; i < length; ++i) {
  746.         tmpptr = thisline;
  747.         thisline = nextline;
  748.         nextline = tmpptr;
  749.         lastline = (i == imax);
  750.         if (fread(inline, 3*width, 1, in) <= 0)
  751.             break;
  752.         inptr = inline;
  753.         nextptr = nextline;
  754.         for (j = 0; j < width; ++j) {
  755.             *nextptr++ = *inptr++;
  756.             *nextptr++ = *inptr++;
  757.             *nextptr++ = *inptr++;
  758.         }
  759.         thisptr = thisline;
  760.         nextptr = nextline;
  761.         outptr = outline;
  762.         for (j = 0; j < width; ++j) {
  763.             int red, green, blue;
  764.             register int oval, r2, g2, b2;
  765.  
  766.             lastpixel = (j == jmax);
  767.             b2 = *thisptr++;
  768.             g2 = *thisptr++;
  769.             r2 = *thisptr++;
  770.             if (r2 < 0)
  771.                 r2 = 0;
  772.             else if (r2 >= MAX_COLOR)
  773.                 r2 = MAX_COLOR-1;
  774.             if (g2 < 0)
  775.                 g2 = 0;
  776.             else if (g2 >= MAX_COLOR)
  777.                 g2 = MAX_COLOR-1;
  778.             if (b2 < 0)
  779.                 b2 = 0;
  780.             else if (b2 >= MAX_COLOR)
  781.                 b2 = MAX_COLOR-1;
  782.             red = r2;
  783.             green = g2;
  784.             blue = b2;
  785.             r2 >>= COLOR_SHIFT;
  786.             g2 >>= COLOR_SHIFT;
  787.             b2 >>= COLOR_SHIFT;
  788.             oval = histogram[r2][g2][b2];
  789.             if (oval == -1) {
  790.                 int ci;
  791.                 register int cj, tmp, d2, dist;
  792.                 register C_cell    *cell;
  793.  
  794.                 cell = *(ColorCells +
  795.                     (((r2>>(B_DEPTH-C_DEPTH)) << C_DEPTH*2) +
  796.                     ((g2>>(B_DEPTH-C_DEPTH)) << C_DEPTH ) +
  797.                     (b2>>(B_DEPTH-C_DEPTH))));
  798.                 if (cell == NULL )
  799.                     cell = create_colorcell(red,
  800.                         green, blue);
  801.                 dist = 9999999;
  802.                 for (ci = 0; ci < cell->num_ents && dist > cell->entries[ci][1]; ++ci) {
  803.                     cj = cell->entries[ci][0];
  804.                     d2 = (rm[cj] >> COLOR_SHIFT) - r2;
  805.                     d2 *= d2;
  806.                     tmp = (gm[cj] >> COLOR_SHIFT) - g2;
  807.                     d2 += tmp*tmp;
  808.                     tmp = (bm[cj] >> COLOR_SHIFT) - b2;
  809.                     d2 += tmp*tmp;
  810.                     if (d2 < dist) {
  811.                         dist = d2;
  812.                         oval = cj;
  813.                     }
  814.                 }
  815.                 histogram[r2][g2][b2] = oval;
  816.             }
  817.             *outptr++ = oval;
  818.             red -= rm[oval];
  819.             green -= gm[oval];
  820.             blue -= bm[oval];
  821.             if (!lastpixel) {
  822.                 thisptr[0] += blue * 7 / 16;
  823.                 thisptr[1] += green * 7 / 16;
  824.                 thisptr[2] += red * 7 / 16;
  825.             }
  826.             if (!lastline) {
  827.                 if (j != 0) {
  828.                     nextptr[-3] += blue * 3 / 16;
  829.                     nextptr[-2] += green * 3 / 16;
  830.                     nextptr[-1] += red * 3 / 16;
  831.                 }
  832.                 nextptr[0] += blue * 5 / 16;
  833.                 nextptr[1] += green * 5 / 16;
  834.                 nextptr[2] += red * 5 / 16;
  835.                 if (!lastpixel) {
  836.                     nextptr[3] += blue / 16;
  837.                         nextptr[4] += green / 16;
  838.                         nextptr[5] += red / 16;
  839.                 }
  840.                 nextptr += 3;
  841.             }
  842.         }
  843.         if (fwrite(outline, width, 1, out) < 0)
  844.             break;
  845.     }
  846.     free(inline);
  847.     free(thisline);
  848.     free(nextline);
  849.     free(outline);
  850. }
  851.  
  852.